{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #把二叉搜索树转换为累加树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: convertBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #把二叉搜索树转换为累加树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><span style=\"font-size:10.5pt\"><span style=\"font-family:Calibri\"><span style=\"font-size:10.5000pt\"><span style=\"font-family:宋体\"><font face=\"宋体\">给定一个二叉搜索树，请将它的每个</font></span></span></span></span>节点<span style=\"font-size:10.5pt\"><span style=\"font-family:Calibri\"><span style=\"font-size:10.5000pt\"><span style=\"font-family:宋体\"><font face=\"宋体\">的值替换成树中大于或者等于该</font></span></span></span></span>节点<span style=\"font-size:10.5pt\"><span style=\"font-family:Calibri\"><span style=\"font-size:10.5000pt\"><span style=\"font-family:宋体\"><font face=\"宋体\">值的所有</font></span></span></span></span>节点<span style=\"font-size:10.5pt\"><span style=\"font-family:Calibri\"><span style=\"font-size:10.5000pt\"><span style=\"font-family:宋体\"><font face=\"宋体\">值之和。</font></span></span></span></span></p>\n",
    "\n",
    "<p style=\"margin:0pt 0pt 0.0001pt; text-align:justify\">&nbsp;</p>\n",
    "\n",
    "<p>提醒一下，二叉搜索树满足下列约束条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点的左子树仅包含键<strong> 小于 </strong>节点键的节点。</li>\n",
    "\t<li>节点的右子树仅包含键<strong> 大于</strong> 节点键的节点。</li>\n",
    "\t<li>左右子树也必须是二叉搜索树。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/05/03/tree.png\" style=\"height: 364px; width: 534px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root<strong> </strong>=<strong> </strong>[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]\n",
    "<strong>输出：</strong>[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0,null,1]\n",
    "<strong>输出：</strong>[1,null,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,0,2]\n",
    "<strong>输出：</strong>[3,3,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,2,4,1]\n",
    "<strong>输出：</strong>[7,9,4,10]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数介于 <code>0</code>&nbsp;和 <code>10<sup>4</sup></code><sup>&nbsp;</sup>之间。</li>\n",
    "\t<li>每个节点的值介于 <code>-10<sup>4</sup></code>&nbsp;和&nbsp;<code>10<sup>4</sup></code>&nbsp;之间。</li>\n",
    "\t<li>树中的所有值 <strong>互不相同</strong> 。</li>\n",
    "\t<li>给定的树为二叉搜索树。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>本题与主站 538&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/convert-bst-to-greater-tree/\">https://leetcode-cn.com/problems/convert-bst-to-greater-tree/</a></li>\n",
    "\t<li>本题与主站 1038&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/\">https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/</a></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [w6cpku](https://leetcode.cn/problems/w6cpku/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [w6cpku](https://leetcode.cn/problems/w6cpku/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]', '[0,null,1]', '[1,0,2]', '[3,2,4,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        p = root\n",
    "        pre = None\n",
    "        while p or stack:\n",
    "            if p:\n",
    "                stack.append(p)\n",
    "                p = p.right\n",
    "            else:\n",
    "                p = stack.pop(-1)\n",
    "                if pre:\n",
    "                    p.val += pre.val\n",
    "                pre = p\n",
    "                p = p.left\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = 0\n",
    "        cur = root\n",
    "        def poor(cur):\n",
    "            if not cur:\n",
    "                return \n",
    "            poor(cur.right)\n",
    "            cur.val += self.pre\n",
    "            self.pre = cur.val\n",
    "            poor(cur.left)\n",
    "        poor(root)\n",
    "\n",
    "        return root\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root: TreeNode):\n",
    "            nonlocal total\n",
    "            if root:\n",
    "                dfs(root.right)\n",
    "                total += root.val\n",
    "                root.val = total\n",
    "                dfs(root.left)\n",
    "        \n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        total=0\n",
    "        def func(root):\n",
    "            nonlocal total\n",
    "            if not root:\n",
    "                None\n",
    "            else:\n",
    "                func(root.right)\n",
    "                total+=root.val\n",
    "                root.val=total\n",
    "                func(root.left)\n",
    "        func(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.total = 0\n",
    "\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.helper1(root)\n",
    "        return root\n",
    "\n",
    "    def helper1(self, root):\n",
    "\n",
    "        if root:\n",
    "            self.helper1(root.right)\n",
    "            self.total += root.val\n",
    "            root.val = self.total\n",
    "            self.helper1(root.left)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.sum = 0\n",
    "        self.helper(root)\n",
    "        return root\n",
    "    \n",
    "    def helper(self, root):\n",
    "        if root is None: return\n",
    "        self.helper(root.right)\n",
    "        root.val += self.sum\n",
    "        self.sum = root.val\n",
    "        self.helper(root.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        count = 0\n",
    "        node = root\n",
    "        while root:\n",
    "            if root.right:\n",
    "                predecessor = root.right\n",
    "                while predecessor.left and predecessor.left != root:\n",
    "                    predecessor = predecessor.left\n",
    "                    pass\n",
    "                if predecessor.left is None:\n",
    "                    predecessor.left = root\n",
    "                    root = root.right\n",
    "                else:\n",
    "                    count += root.val\n",
    "                    root.val = count\n",
    "                    predecessor.left = None\n",
    "                    root = root.left\n",
    "                pass\n",
    "            else:\n",
    "                count += root.val\n",
    "                root.val = count\n",
    "                root = root.left\n",
    "            pass\n",
    "        return node\n",
    "    pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        head = root\n",
    "        stack = []\n",
    "        res = 0\n",
    "        while root or stack:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.right\n",
    "            root = stack.pop()\n",
    "            res += root.val\n",
    "            root.val = res\n",
    "            root = root.left\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root: TreeNode):\n",
    "            nonlocal total\n",
    "            if root:\n",
    "                dfs(root.right)\n",
    "                total += root.val\n",
    "                root.val = total\n",
    "                dfs(root.left)\n",
    "        \n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.sum = 0\n",
    "        self.helper(root)\n",
    "        return root\n",
    "\n",
    "    def helper(self, root):\n",
    "        if root is None:\n",
    "            return\n",
    "        self.helper(root.right)\n",
    "        root.val += self.sum\n",
    "        self.sum = root.val\n",
    "        self.helper(root.left)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "            s = 0\n",
    "            node = root\n",
    "            while root:\n",
    "                if root.right is None:\n",
    "                    s += root.val\n",
    "                    root.val = s\n",
    "                    root = root.left\n",
    "                else:\n",
    "                    next = root.right\n",
    "                    while next.left and next.left != root:\n",
    "                        next = next.left\n",
    "                    if next.left is None:\n",
    "                        next.left = root\n",
    "                        root = root.right\n",
    "                    else:\n",
    "                        s += root.val\n",
    "                        root.val = s \n",
    "                        next.left = None\n",
    "                        root = root.left\n",
    "            return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.sum = 0\n",
    "        self.traverse(root)\n",
    "        return root\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.traverse(root.right)\n",
    "        self.sum += root.val\n",
    "        root.val = self.sum\n",
    "        self.traverse(root.left)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        prefix = 0\n",
    "        def dfs(node: TreeNode):\n",
    "            if node.right:\n",
    "                dfs(node.right)\n",
    "            \n",
    "            nonlocal prefix\n",
    "            prefix += node.val\n",
    "            node.val = prefix\n",
    "\n",
    "            if node.left:\n",
    "                dfs(node.left)\n",
    "        if root:\n",
    "            dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.summ=0\n",
    "        self.helper(root)\n",
    "        return root\n",
    "\n",
    "    def helper(self, root):\n",
    "        if not root:return\n",
    "        self.helper(root.right)\n",
    "        root.val+=self.summ\n",
    "        self.summ=root.val\n",
    "        self.helper(root.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.total = 0 \n",
    "        def dfs(root):\n",
    "            if root:\n",
    "                dfs(root.right)\n",
    "                self.total += root.val\n",
    "                root.val = self.total \n",
    "                dfs(root.left)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return root  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        sm = 0\n",
    "        def inorder(root):\n",
    "            nonlocal sm\n",
    "            if not root:\n",
    "                return\n",
    "            inorder(root.right)\n",
    "            sm += root.val\n",
    "            root.val = sm\n",
    "            inorder(root.left)\n",
    "        inorder(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        total = 0 \n",
    "        def dfs (root):\n",
    "            nonlocal total\n",
    "            if root is None:\n",
    "                return \n",
    "            else :\n",
    "                dfs(root.right)\n",
    "                total+=root.val\n",
    "                root.val = total  #反序遍历中序遍历\n",
    "                dfs(root.left)    #从最右边开始加\n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.res=0\n",
    "\n",
    "        def recur(root):\n",
    "            if not root:return \n",
    "            recur(root.right)\n",
    "\n",
    "            self.res+= int(root.val)\n",
    "            root.val = (self.res)\n",
    "            recur(root.left)\n",
    "        \n",
    "\n",
    "        recur(root)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.sum = 0\n",
    "        def convert(root):\n",
    "            if not root:\n",
    "                return\n",
    "            convert(root.right)\n",
    "            root.val += self.sum\n",
    "            self.sum = root.val\n",
    "            convert(root.left)\n",
    "        convert(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = 0\n",
    "        cur = root\n",
    "        def poor(cur):\n",
    "            if not cur:\n",
    "                return \n",
    "            poor(cur.right)\n",
    "            cur.val += self.pre\n",
    "            self.pre = cur.val\n",
    "            poor(cur.left)\n",
    "        poor(root)\n",
    "\n",
    "        return root\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        pre = 0\n",
    "        def dfs(cur):\n",
    "            if not cur:\n",
    "                return\n",
    "            nonlocal pre\n",
    "            dfs(cur.right)\n",
    "            cur.val += pre\n",
    "            pre = cur.val\n",
    "            dfs(cur.left)\n",
    "        dfs(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def search(root, num):\n",
    "            if root.right:\n",
    "                num = search(root.right, num)\n",
    "            num+=root.val\n",
    "            root.val=num\n",
    "            if root.left:\n",
    "                num = search(root.left, num)\n",
    "            return num\n",
    "        if root:search(root, 0)\n",
    "        return root\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return None\n",
    "        self.inorder_traversal(root, 0)\n",
    "        return root\n",
    "\n",
    "    def inorder_traversal(\n",
    "        self,\n",
    "        root: Optional[TreeNode],\n",
    "        parent_sum: int,\n",
    "    ) -> int:\n",
    "        right_sum = 0\n",
    "        if root.right is not None:\n",
    "            right_sum = self.inorder_traversal(root.right, parent_sum)\n",
    "        left_sum = 0\n",
    "        if root.left is not None:\n",
    "            left_sum = self.inorder_traversal(\n",
    "                root.left,\n",
    "                parent_sum + right_sum + root.val,\n",
    "            )\n",
    "        ret_val = root.val + right_sum + left_sum\n",
    "        root.val += right_sum + parent_sum\n",
    "        return ret_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#二叉搜索树的中序遍历（左根右）结果是一个单调递增的有序序列，我们反序进行中序遍历（右根左），即可以得到一个单调递减的有序序列。通过累加单调递减的有序序列，我们可以得到大于等于 node.val 的新值，并重新赋值给 node。\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.total=0\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        if root==None:\n",
    "            return \n",
    "        self.dfs(root)\n",
    "        return root\n",
    "\n",
    "    def dfs(self,root):\n",
    "        if root==None:\n",
    "            return\n",
    "        self.dfs(root.right)\n",
    "        self.total+=root.val\n",
    "        root.val=self.total\n",
    "        self.dfs(root.left)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.sum = 0\n",
    "        self.traverset(root)\n",
    "        return root\n",
    "    \n",
    "\n",
    "    def traverset(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        \n",
    "        self.traverset(root.right)\n",
    "        self.sum += root.val\n",
    "        root.val = self.sum\n",
    "\n",
    "        self.traverset(root.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        res = 0\n",
    "        def search(root):\n",
    "            if not root:\n",
    "                return \n",
    "            nonlocal res\n",
    "            search(root.right)\n",
    "            res += root.val\n",
    "            root.val = res\n",
    "            search(root.left)\n",
    "        search(root)\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        total = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal total\n",
    "            if not node:\n",
    "                return \n",
    "            dfs(node.right)\n",
    "            total += node.val \n",
    "            node.val = total\n",
    "            dfs(node.left)\n",
    "        \n",
    "        dfs(root)\n",
    "        return root "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.c = 0\n",
    "        def chk(r):\n",
    "            if not r:\n",
    "                return\n",
    "            chk(r.right)\n",
    "            self.c += r.val\n",
    "            r.val = self.c\n",
    "            chk(r.left)\n",
    "        chk(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        current = 0\n",
    "        def dfs(n: TreeNode):\n",
    "            nonlocal current\n",
    "            if n is None:\n",
    "                return\n",
    "            dfs(n.right)\n",
    "            current += n.val\n",
    "            n.val = current\n",
    "            dfs(n.left)\n",
    "        dfs(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        method = 'mine'\n",
    "        if method == 'mine':\n",
    "            def dfs(node):\n",
    "                if not node: \n",
    "                    return\n",
    "                dfs(node.right)\n",
    "                self.sum += node.val\n",
    "                node.val = self.sum\n",
    "                dfs(node.left)\n",
    "            self.sum = 0\n",
    "            dfs(root)\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        sum = [0]\n",
    "\n",
    "        def traverse(root: Optional[TreeNode]) -> None:\n",
    "            \"\"\" bst的遍历框架(但逆序->递减排列) \"\"\"\n",
    "\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            traverse(root.right)\n",
    "            sum[0] += root.val             # 更新维护sum\n",
    "            root.val = sum[0]              # 利用bst特性进行值转换\n",
    "            traverse(root.left)\n",
    "\n",
    "        traverse(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.acc = 0\n",
    "\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "        self.convertBST(root.right)\n",
    "        self.acc += root.val\n",
    "        root.val = self.acc\n",
    "        self.convertBST(root.left)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-66994/dong-ge-da-8f403/\n",
    "# 累加和是计算大于等于当前值的所有元素之和。比如示例1里，5节点，>=5的节点就是5 6 7 8，这4个数加起来=26，所以5节点的累加和就是26\n",
    "\n",
    "# 降序打印节点的值：中序遍历的递归顺序改一下\n",
    "# 代码短小精悍，非常巧妙，没做过真的想不到。而且是原地修改，空间复杂度也很小\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sum = 0\n",
    "\n",
    "    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "        self.traverse(root)\n",
    "        \n",
    "        return root\n",
    "    \n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return None # 这里是return 还是return None呢，有个技巧，看这个函数定义的返回值，本题给的返回值是TreeNode，那就是return None\n",
    "        \n",
    "        # 先循环right，再循环left，就是降序的意思\n",
    "        self.traverse(root.right)\n",
    "        self.sum += root.val\n",
    "        root.val = self.sum\n",
    "        self.traverse(root.left)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def inOrder(root):\n",
    "            nonlocal res\n",
    "            if not root: return \n",
    "            inOrder(root.right)\n",
    "            res += root.val\n",
    "            root.val = res\n",
    "            inOrder(root.left)\n",
    "        res = 0\n",
    "        inOrder(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(node):\n",
    "            nonlocal total\n",
    "            if node:\n",
    "                dfs(node.right)\n",
    "                total += node.val\n",
    "                node.val = total\n",
    "                dfs(node.left)\n",
    "\n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.total = 0\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            dfs(root.right)\n",
    "            self.total += root.val\n",
    "            root.val = self.total\n",
    "            dfs(root.left)\n",
    "        \n",
    "        dfs(root)\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # self.total = 0\n",
    "        # def dfs(root):\n",
    "        #     if not root: return \n",
    "        #     dfs(root.right)\n",
    "        #     self.total += root.val\n",
    "        #     root.val = self.total\n",
    "        #     dfs(root.left)\n",
    "\n",
    "       \n",
    "        # dfs(root)\n",
    "        # return root\n",
    "\n",
    "\n",
    "\n",
    "        # def dfs(root):\n",
    "        #     if not root: return None\n",
    "        #     nonlocal total\n",
    "        #     dfs(root.right)\n",
    "        #     total += root.val\n",
    "        #     root.val = total\n",
    "        #     dfs(root.left)\n",
    "\n",
    "        # total = 0\n",
    "        # dfs(root)\n",
    "        # return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root):\n",
    "            nonlocal result\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            dfs(root.right)\n",
    "            result+=root.val\n",
    "            root.val=result\n",
    "            dfs(root.left)\n",
    "            \n",
    "\n",
    "        result=0\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self,root,s):\n",
    "        if not root:\n",
    "            return s\n",
    "        s = self.dfs(root.right,s)\n",
    "        s += root.val\n",
    "        root.val = s\n",
    "        s = self.dfs(root.left,s)\n",
    "        return s\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.dfs(root,0)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        sum_val = 0\n",
    "        def helper(node):\n",
    "            nonlocal sum_val\n",
    "            if node is None:return node\n",
    "            helper(node.right)\n",
    "            sum_val+=node.val\n",
    "            node.val = sum_val\n",
    "            helper(node.left)\n",
    "        helper(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "\n",
    "        node_list = []\n",
    "        cur = root\n",
    "        sum = 0\n",
    "        while node_list or cur:\n",
    "            while cur:\n",
    "                node_list.append(cur)\n",
    "                cur = cur.right\n",
    "\n",
    "            cur = node_list.pop()\n",
    "\n",
    "            sum += cur.val\n",
    "            cur.val = sum\n",
    "\n",
    "            cur = cur.left\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root: TreeNode):\n",
    "            nonlocal total\n",
    "            if root:\n",
    "                dfs(root.right)\n",
    "                total += root.val\n",
    "                root.val = total\n",
    "                dfs(root.left)\n",
    "        \n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sum = 0\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return\n",
    "            traverse(root.right)\n",
    "            self.sum += root.val\n",
    "            root.val = self.sum\n",
    "            traverse(root.left)\n",
    "        traverse(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        t=0\n",
    "        def midbl(p):\n",
    "            if p is None: return\n",
    "            if p.right:\n",
    "                midbl(p.right)\n",
    "            nonlocal t\n",
    "            p.val=t+p.val\n",
    "            t=p.val\n",
    "            if p.left:\n",
    "                midbl(p.left)\n",
    "        midbl(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.sum=0\n",
    "        self.recur(root)\n",
    "        return root\n",
    "    def recur(self,root):\n",
    "        if not root:\n",
    "            return \n",
    "        self.recur(root.right)\n",
    "        self.sum+=root.val\n",
    "        root.val=self.sum\n",
    "        self.recur(root.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root: TreeNode):\n",
    "            nonlocal total\n",
    "            if root:\n",
    "                dfs(root.right)\n",
    "                total += root.val\n",
    "                root.val = total\n",
    "                dfs(root.left)\n",
    "        \n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root: TreeNode, val: int) -> int:\n",
    "            if root == None:\n",
    "                return 0\n",
    "\n",
    "            if root.left == None and root.right == None:\n",
    "                root.val += val\n",
    "                return root.val\n",
    "\n",
    "            t = 0\n",
    "            if root.right != None:\n",
    "                t = dfs(root.right, val)\n",
    "                root.val += t\n",
    "            else:\n",
    "                root.val += val\n",
    "            if root.left != None:\n",
    "                return dfs(root.left, root.val)\n",
    "            return root.val\n",
    "\n",
    "        dfs(root, 0)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        total = 0 \n",
    "        def dfs (root):\n",
    "            nonlocal total\n",
    "            if root is None:\n",
    "                return \n",
    "            else :\n",
    "                dfs(root.right)\n",
    "                total+=root.val\n",
    "                root.val = total  #反序遍历中序遍历\n",
    "                dfs(root.left)    #从最右边开始加\n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    val = 0\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return\n",
    "        self.convertBST(root.right)\n",
    "        self.val += root.val\n",
    "        root.val = self.val\n",
    "        self.convertBST(root.left)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        sum=0\n",
    "        def a(root:TreeNode):\n",
    "            nonlocal sum\n",
    "            if root:\n",
    "               a(root.right)\n",
    "               sum+=root.val\n",
    "               root.val=sum\n",
    "               a(root.left)\n",
    "\n",
    "        a(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        s = 0\n",
    "        def dfs(node):\n",
    "            nonlocal s\n",
    "            if not node:\n",
    "                return \n",
    "            dfs(node.right)\n",
    "            node.val += s\n",
    "            s = node.val\n",
    "            dfs(node.left)\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        pre = 0\n",
    "        def posteriorOrder(root):\n",
    "            nonlocal pre\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            posteriorOrder(root.right)\n",
    "            root.val += pre\n",
    "            pre = root.val\n",
    "            posteriorOrder(root.left)\n",
    "        posteriorOrder(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        Sum = 0\n",
    "        cur = root \n",
    "        stack = []\n",
    "        while cur != None or stack:\n",
    "            while cur != None:\n",
    "                stack.append(cur)\n",
    "                cur = cur.right\n",
    "            \n",
    "            cur = stack.pop()\n",
    "            Sum += cur.val\n",
    "            cur.val = Sum\n",
    "            cur = cur.left\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        total = 0 \n",
    "        def dfs (root):\n",
    "            nonlocal total\n",
    "            if root is None:\n",
    "                return \n",
    "            else :\n",
    "                dfs(root.right)\n",
    "                total+=root.val\n",
    "                root.val = total  #反序遍历中序遍历\n",
    "                dfs(root.left)    #从最右边开始加\n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.sum = 0\n",
    "        def traverse(node):\n",
    "            if not node:\n",
    "                return\n",
    "            traverse(node.right)\n",
    "            self.sum += node.val\n",
    "            node.val = self.sum\n",
    "            traverse(node.left)\n",
    "        traverse(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        #copy\n",
    "        def dfs(root):\n",
    "            nonlocal s\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.right)\n",
    "            s+= root.val\n",
    "            root.val = s\n",
    "            dfs(root.left)\n",
    "        s =0\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sumnum=0\n",
    "    \n",
    "    def convertBST(self, root) :\n",
    "        self.debacktravel(root)\n",
    "        return root\n",
    "    def debacktravel(self,root):\n",
    "        while root==None:\n",
    "            return 0\n",
    "        self.debacktravel(root.right)\n",
    "        self.sumnum+=root.val\n",
    "        root.val=self.sumnum\n",
    "        self.debacktravel(root.left)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        count = 0\n",
    "        def dfs(node):\n",
    "            nonlocal count\n",
    "            if node is None:\n",
    "                return 0\n",
    "            dfs(node.right)\n",
    "            count = node.val + count\n",
    "            node.val = count\n",
    "            dfs(node.left)\n",
    "            return count\n",
    "        dfs(root)\n",
    "        return root\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        def dfs(node, load):\n",
    "            if node == None:\n",
    "                return\n",
    "            dfs(node.right, load)\n",
    "            node.val += load[0]\n",
    "            load[0] = node.val\n",
    "            dfs(node.left, load)\n",
    "        dfs(root, [0])\n",
    "        return root\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root: TreeNode):\n",
    "            nonlocal total\n",
    "            if root:\n",
    "                dfs(root.right)\n",
    "                total += root.val\n",
    "                root.val = total\n",
    "                dfs(root.left)\n",
    "        \n",
    "        total = 0\n",
    "        dfs(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        self.csum_val=0\n",
    "        def csum(root):\n",
    "            if root:\n",
    "                csum(root.right)\n",
    "                self.csum_val +=root.val\n",
    "                root.val = self.csum_val\n",
    "                csum(root.left)\n",
    "\n",
    "        csum(root)\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return \n",
    "        ##\n",
    "        def dfs(tree):\n",
    "            nonlocal val \n",
    "            if not tree:\n",
    "                return \n",
    "            dfs(tree.right)\n",
    "            val += tree.val \n",
    "            tree.val = val \n",
    "            dfs(tree.left)\n",
    "        ##\n",
    "        val = 0\n",
    "        dfs(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def convertBST(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root):\n",
    "            nonlocal s\n",
    "            if root is None:\n",
    "                return\n",
    "            dfs(root.right)\n",
    "            s += root.val\n",
    "            root.val = s\n",
    "            dfs(root.left)\n",
    "\n",
    "        s = 0\n",
    "        dfs(root)\n",
    "        return root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
